package com.ruoyi.learn.java.algorithm.graph;

import java.util.*;


/**
 * 当然可以！N 皇后问题 是深度优先搜索（DFS）与回溯法（Backtracking） 的经典应用。
 * 目标是在一个 N×N 的棋盘上放置 N 个皇后，
 * 使得任意两个皇后都不能在同一行、同一列或同一对角线上。
 *
 * 🧩 问题描述（LeetCode 51. N-Queens）
 * 输入：n = 4
 *
 * 输出：所有满足条件的皇后摆放方案（以棋盘形式表示）
 *
 * ✅ 解题思路
 * 逐行放置皇后：每一行只能放一个皇后，所以我们可以从第 0 行到第 n-1 行依次尝试。
 * 列、主对角线、副对角线去重：
 * 使用 boolean[] cols 记录已占用的列。
 * 主对角线（从左上到右下）：同一对角线上的坐标满足 row - col 为常数。
 * 副对角线（从右上到左下）：同一对角线上的坐标满足 row + col 为常数。
 * 回溯：如果当前列不能放，就尝试下一列；如果所有列都失败，回退到上一行重新选择。
 *
 *
 * 八皇后问题
 * 当然可以！八皇后问题 是 N 皇后问题 的特例（N = 8），是经典的回溯算法（Backtracking）应用。目标是在 8×8 的国际象棋棋盘上放置 8 个皇后，使得它们互不攻击（即：任意两个皇后不能在同一行、同一列、同一主对角线或副对角线上）。
 *
 * ✅ Java 完整代码实现（八皇后问题）
 * 下面是一个完整的 Java 程序，输出所有 92 种解法，并以可视化方式打印棋盘。
 */
public class EightQueens {

    private static final int N = 8; // 八皇后
    private static List<char[][]> solutions = new ArrayList<>();

    public static void main(String[] args) {
        // 初始化棋盘
        char[][] board = new char[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(board[i], '.');
        }

        // 标记占用状态
        boolean[] cols = new boolean[N];        // 列
        boolean[] diag1 = new boolean[2 * N - 1]; // 主对角线: row - col + 7
        boolean[] diag2 = new boolean[2 * N - 1]; // 副对角线: row + col

        solve(board, 0, cols, diag1, diag2);

        // 输出结果
        System.out.println("八皇后问题共有 " + solutions.size() + " 种解法：\n");

        // 打印前几个解法（可选全部打印）
        int printCount = Math.min(1000000, solutions.size()); // 只打印前5个解法，避免输出太多
        for (int i = 0; i < printCount; i++) {
            System.out.println("解法 " + (i + 1) + ":");
            printBoard(solutions.get(i));
        }

        if (solutions.size() > printCount) {
            System.out.println("... 还有 " + (solutions.size() - printCount) + " 种解法未显示");
        }
    }

    /**
     * 使用回溯法求解八皇后问题
     * @param board 棋盘
     * @param row 当前行
     * @param cols 列占用状态
     * @param diag1 主对角线占用状态 (row - col + 7)
     * @param diag2 副对角线占用状态 (row + col)
     */
    private static void solve(char[][] board, int row, boolean[] cols, boolean[] diag1, boolean[] diag2) {
        // 终止条件：已经处理完第 0~7 行
        if (row == N) {
            // 保存当前解（深拷贝）
            char[][] solution = new char[N][N];
            for (int i = 0; i < N; i++) {
                System.arraycopy(board[i], 0, solution[i], 0, N);
            }
            solutions.add(solution);
            return;
        }

        // 尝试在当前行的每一列放置皇后
        for (int col = 0; col < N; col++) {
            int d1 = row - col + N - 1; // 主对角线索引 [0, 14]
            int d2 = row + col;         // 副对角线索引 [0, 14]

            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue; // 冲突，跳过
            }

            // 做选择
            board[row][col] = 'Q';
            cols[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;

            // 递归下一行
            solve(board, row + 1, cols, diag1, diag2);

            // 回溯：撤销选择
            board[row][col] = '.';
            cols[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }

    /**
     * 打印棋盘
     */
    private static void printBoard(char[][] board) {
        for (char[] row : board) {
            System.out.println(Arrays.toString(row).replaceAll(",", " ").replaceAll(" ", ""));
        }
        System.out.println();
    }
}